Dragon Warrior II/III/IV (NES) Map Building Visualizer
by abw
Version 1.0
2021-04-03

The NES games Dragon Warrior II, Dragon Warrior III, and Dragon Warrior IV have an interesting way of storing their non-overworld maps on cartridge ROM. While the original Dragon Warrior stores the final layout of its maps using a simple compression algorithm, the map data for the later NES games is stored as a list of instructions for building the final map based on a small set of supported operations. These operations have been re-implemented in javascript and paired with an (offline) HTML5/CSS3 page for visualizing their effects with appropriate tilesets from the games partly as an aid to understanding how the binary map data produces the final map layout and partly because there's an odd sort of beauty in watching the maps being incrementally constructed from scratch one piece at a time. In addition to coming preloaded with all of the non-overworld maps from each of these games and displaying various potentially interesting statistics about them, arbitrary new map data can be entered and the corresponding map built following the same process as the games' actual maps, so although this is not really a map editor, it can be used as a quick way to validate map data that has been created elsewhere.


Map Data Format
===============

The primary data for each map starts with 24 bits of setup data:
	8 bits				map width
	8 bits				map height
	2 bits				tile ID size - 2 (i.e. the actual size is this value + 2)
	6 bits				unused data

Based on the map dimensions, the size of a map co-ordinate is effectively calculated as ceil(log2(width * height)), i.e. the minimum number of bits required to index into a width * height array (e.g. a map which is 8 tiles wide and 10 tiles high contains 80 tiles and requires 7 bits to uniquely identify each tile). The final setup step is to choose a tile ID to be used as the background; the map will be initialized as a single (map width) * (map height) rectangle of this tile ID:
	(tile ID size) bits		background tile ID

After that, the map is constructed in 3 phases:
	- The first phase sequentially executes a list of building instructions that place the base tiles in their desired positions.
	- The second phase is much like the first phase in that it also sequentially executes a list of building instructions, but it is optional and instead of placing base tiles it divides the map up into different visibility regions.
	- The third phase happens automatically (i.e. it does not appear in the map data) and processes the current map state to convert wall tiles that are the bottom of a wall (i.e. wall tiles that do not have another wall tile below them) from vertical wall tiles to horizontal wall tiles.

The primary map building instructions are:
	00				update current tile ID(s)
	01				draw a rectangle between two points
	10				draw tile ID(s) from a point in a direction
	11				draw tile ID(s) at a point

Primary Map Building Instruction 00
-----------------------------------
Updating the current tile ID(s) first selects a single tile ID:
	(tile ID size)			set tile ID 1
After selecting the first tile ID, if the next primary map building instruction is to update the current tile ID(s) again (i.e. 00), there is a 1 bit choice between ending the current map building phase (this is how the main building instruction loop exits) and reading 3 more tile IDs:
	000				read 3 more tile IDs
	001				end current map building phase
- When reading 3 more tile IDs, a further 3 tile IDs are selected which together with the first tile ID are arranged to form a 2x2 tile group with tile 1 in the top left, tile 2 in the top right, tile 3 in the bottom left, and tile 4 in the bottom right position:
	(tile ID size) bits		set tile ID 2
	(tile ID size) bits		set tile ID 3
	(tile ID size) bits		set tile ID 4
- When switching from phase 1 (base tiles) to phase 2 (visibility regions), the tile ID size is updated; if the new tile ID size is 0, then phase 2 is skipped, otherwise construction continues with the next primary map building instruction, but now affecting visibility regions instead of base tiles:
	2 bits				tile ID size

Primary Map Building Instruction 01
-----------------------------------
Drawing a rectangle between two points requires specifying the two points:
	(map co-ordinate size) bits	point 1
	(map co-ordinate size) bits	point 2
The 2 points are converted from array indices to (X, Y) co-ordinates and then the rectangle formed by using the first point as the top-left corner and the second point as the bottom-right corner (i.e. (X1, Y1) to (X2, Y2)) is filled with the currently selected 1x1 or 2x2 tile group. When drawing with a 2x2 tile group, the tile groups are placed adjacent to each other so that they do not overlap and the rectangle dimensions should all be an even number of tiles.

Primary Map Building Instruction 10
-----------------------------------
Drawing tile ID(s) from a point in a direction is the most complicated operation. It first requires specifying the starting point:
	(map co-ordinate size) bits	point
and then 1 of 4 possible directions:
	00				up
	01				right
	10				down
	11				left
after which the currently selected 1x1 or 2x2 tile group is drawn at the specified point and map building continues by executing line drawing instructions:
	0				move and draw
	100				rotate clockwise, move, and draw
	101				rotate counter-clockwise, move, and draw
	1100				push map data, rotate clockwise, move, and draw
	1101				push map data, rotate counter-clockwise, move, and draw
	1110				update map position and direction
	1111				pop map data
- Moving and drawing first updates the current drawing point by moving 1 or 2 tiles (depending on the number of tiles currently selected) in the current direction and then drawing a 1x1 or 2x2 tile group at the new point.
- Rotating changes the current direction to the next clockwise (e.g. from up to right) or counter-clockwise (e.g. from right to up) direction; there is no single instruction for reversing (e.g. from up to down) the direction.
- Pushing map data onto the map stack stores a copy of the current position and direction on the map stack for later retrieval.
- Updating the map position and direction allows the drawing to jump from one point to another without affecting any intermediate points; it must be followed by a new starting point:
	(map co-ordinate size) bits	point
and then 1 of 4 possible directions:
	00				up
	01				right
	10				down
	11				left
- Popping map data from the map stack retrieves previously pushed data in the opposite order from which it was pushed (a stack is a First In, Last Out [FIFO] data structure, so if data is pushed in the order A then B then C, it will be popped in the order C then B then A). Popping an empty stack ends the line drawing instructions and map building continues with the next primary map building instruction.

Primary Map Building Instruction 11
-----------------------------------
Drawing tile ID(s) at a point requires specifying the point:
	(map co-ordinate size)		point
The point is considered the top-left corner of a 1x1 or 2x2 rectangle depending on the number of tiles currently selected and is filled with the currently selected 1x1 or 2x2 tile group.


Map Cost Analysis
=================
Here's a little convenience chart for calculating the cost in bits of drawing a map based on the chosen operations:
	Cost:				Operation:
	24 + (tile ID size)		setup
	2 + (tile ID size)		update current tile ID(s) (1x1)
	5 + 4 * (tile ID size)		update current tile ID(s) (2x2)
	2 + 2 * (map co-ordinate size)	draw a rectangle between two points
	8 + (map co-ordinate size)	draw tile ID(s) from a point in a direction
	1 * (number of tiles)		move and draw
	3 * (number of rotations)	rotate, move and draw
	8 * (number of pushes)		push map data, rotate, move, and draw
	6 + (map co-ordinate size)	update map position and direction
	2 + (map co-ordinate size)	draw tile ID(s) at a point
	5 + (tile ID size)		end a phase
	2				start phase 2
The minimum cost of a map is thus 31 + 2 * (tile ID size) bits and grows arbitrarily based on the operations used to generate the final layout.


TBD/Errata:
===========
- add appropriate palette variants for each tileset (e.g. in DW3, Aliahan and [pre-ending] Tantegel share the same tileset but use different palettes)
- re-convert walls when switching displayed visibility region
- apply better show/hide logic for tiles that "peek through" visibility regions
- come up with an algorithm for generating an optimal (with respect to binary length) set of building instructions
- build a map editor